package hot100;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class Solution56 {
    public int[][] merge(int[][] intervals) {
        if (intervals == null) {
            return null;
        }
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> ans = new LinkedList<>();
        int left = intervals[0][0];
        int right = intervals[0][1];
        int len = 0;
        ans.add(new int[]{left, right});
        for (int i = 1; i < intervals.length; i++) {
            int[] interval = intervals[i];
            if (interval[0] > right) {
                ans.add(new int[]{interval[0], interval[1]});
                left = interval[0];
                right = interval[1];
            } else {
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
                ans.remove(ans.size() - 1);
                ans.add(new int[]{left, right});
            }
        }
        return ans.toArray(new int[0][]);
    }

    public static void main(String[] args) {
        Solution56 solution56 = new Solution56();
        int[][] input = new int[][] {
            {2,6},
            {1,3},
            {8,10},
            {15,18}
        };
        int[][] merge = solution56.merge(input);
    }
}
